package TDAGrafo;

import TDACola.TCola;
import TDALista.TElemento;
import TDALista.TLista;


/**
 * @author 206
 * @version 0.0 
 */
public class TGrafoNoDirigido {

	public TLista vertices = new TLista();

	/**
	 * @param unaEtiqueta
	 * @return True si se pudo insertar el vertice, false en caso contrario
	 */
	@SuppressWarnings("rawtypes")
	public boolean insertarVertice(Comparable unaEtiqueta) {

		if (existeVertice(unaEtiqueta)) {
			return false;
		}
		TVertice vert = new TVertice(unaEtiqueta);
		TElemento elem = new TElemento(unaEtiqueta, vert);
		vertices.insertarAlFinal(elem);
		return true;
	}

	/**
	 * @param etiquetaOrigen
	 * @param etiquetaDestino
	 * @param costo
	 * @return True si se pudo insertar la adyacencia, false en caso contrario
	 */
	@SuppressWarnings("rawtypes")
	public boolean insertarAdyacencia(Comparable etiquetaOrigen, Comparable etiquetaDestino, Comparable costo) {

		TVertice origen = buscarVertice(etiquetaOrigen);
		if (origen != null) {
			TVertice destino = buscarVertice(etiquetaDestino);
			if (destino == null) {
				return false;
			}

			TAdyacencia nueva = new TAdyacencia(destino, costo);
			TAdyacencia nueva2 = new TAdyacencia(origen, costo);


			return origen.insertarAdyacencia(nueva) && destino.insertarAdyacencia(nueva2);


		}
		return false;
	}

	/**
	 * @param unaEtiqueta
	 * @return True si existe el vertice con la etiqueta indicada, false en caso contrario
	 */
	@SuppressWarnings("rawtypes")
	public boolean existeVertice(Comparable unaEtiqueta) {
		return (buscarVertice(unaEtiqueta) != null);
	}

	/**
	 *
	 * @param unaEtiqueta
	 * @return El vertice identificado por el comparable "unaEtiqueta"
	 */
	@SuppressWarnings("rawtypes")
	public TVertice buscarVertice(Comparable unaEtiqueta) {
		TElemento elem = vertices.buscarEtiqueta(unaEtiqueta);
		if (elem != null) {
			return (TVertice) elem.datos;
		}
		return null;
	}

	/**
	 * @param etiquetaOrigen
	 * @param etiquetaDestino
	 * @return True si existe la adyacencia, false en caso contrario
	 */
	@SuppressWarnings("rawtypes")
	public boolean existeAdyacencia(Comparable etiquetaOrigen, Comparable etiquetaDestino) {

		TVertice origen = buscarVertice(etiquetaOrigen);
		if (origen != null) {
			for (TElemento actual = origen.adyacentes.primero; actual != null; actual = actual.siguiente) {
				if (((TAdyacencia) actual.datos).destino.etiqueta.equals(etiquetaDestino)) {
					return true;
				}
			}

			return false;
		}




		return false;

	}

	/**
	 *
	 * @param nombreVertice
	 * @return
	 */
	@SuppressWarnings("rawtypes")
	public boolean eliminarVertice(Comparable nombreVertice) {

		boolean aretornar = vertices.eliminarEtiqueta(nombreVertice);
		TElemento aux = vertices.primero;

		while (aux != null) {
			TVertice aux2 = (TVertice) aux.datos;
			if (aux2.adyacentes.eliminarEtiqueta(nombreVertice)) {
				aretornar = true;
			}

			aux = aux.siguiente;
		}


		return aretornar;
	}

	@SuppressWarnings("rawtypes")
	public boolean eliminarAdyacencia(Comparable nomVerticeOrigen, Comparable nomVerticeDestino) {
		TVertice origen = buscarVertice(nomVerticeOrigen);

		if (origen != null) {
			TVertice destino = buscarVertice(nomVerticeDestino);
			if (destino != null) {
				return (origen.adyacentes.eliminarEtiqueta(nomVerticeDestino)) && destino.adyacentes.eliminarEtiqueta(nomVerticeOrigen);
			}



		}
		return false;

	}

	public void desvisitar() {

		for (TElemento aux = vertices.primero; aux != null; aux = aux.siguiente) {

			TVertice actual = (TVertice) aux.datos;
			actual.visitado = false;
		}
	}

	@SuppressWarnings("rawtypes")
	public Comparable[] bpf(Comparable etiquetaOrigen) {

		TCamino camino = new TCamino();
		desvisitar();
		TVertice origen = buscarVertice(etiquetaOrigen);
		if (origen ==null)
			return null;
		if (origen != null) {
			camino.origen = origen;
			origen.bpfinterno(camino);

		}

		return camino.mostrarCamino();

	}

	@SuppressWarnings("rawtypes")
	public Comparable[] bea(Comparable etiquetaOrigen) {

		TVertice origen = buscarVertice(etiquetaOrigen);
		if (origen == null) {
			return null;
		}

		desvisitar();
		TCamino camino = new TCamino();
		TCola cola = new TCola();
		camino.origen = origen;
		origen.visitado=true;
		TElemento encolado = new TElemento(origen.etiqueta, origen);
	    cola.push(encolado);

		while (!cola.esVacia()){
			TVertice vertice = (TVertice) cola.pop().datos;
			

			for (TElemento aux = vertice.adyacentes.primero; aux!=null; aux= aux.siguiente) {
				TAdyacencia actual = (TAdyacencia) aux.datos;
				if (!actual.destino.visitado) {
					actual.destino.visitado = true;
					cola.push(new TElemento(actual.destino.etiqueta, actual.destino));
					camino.recorrido(actual);
				}
			}

		}

		return camino.mostrarCamino();

	}
}
